import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * @author WangTianyi
 * @create 2021-12-08 18:24
 */
public class MergeSort {
    /*
    王添翼手记：理解二路归并排序时，一定要先在脑海中回忆一下线性表中的一道题：
    将两个非升序的线性表合并为一个非升序的顺序表。
    这是理解二路归并排序的前提，尤其有助于理解为什么Pro版本要把右边的数组倒置
    理解需要倒置的原因时，在纸上举例子模拟是个非常好的方法。
     */
    private static final int THRESHOLD = 28;
    public static void main(String[] args) {
        int length = 5000000;
        Integer[] array1 = new Integer[length];
        Integer[] array2 = new Integer[length];
        Integer[] array3 = new Integer[length];
        Integer[] tempArray1 = new Integer[length];
        Integer[] tempArray2 = new Integer[length];
        Integer[] tempArray3 = new Integer[length];
        for (int i = 0; i < array1.length; i++) {
            array1[i] = array2[i] = (int) (Math.random()*(100-0+1));
        }
        System.arraycopy(array1, 0, array2, 0, length);
        System.arraycopy(array1, 0, array3, 0, length);

        long start1 = System.currentTimeMillis();
        mergeSort(array1, tempArray1, 0, length-1);
        long end1 = System.currentTimeMillis();
//        System.out.println(Arrays.toString(array1));

        long start2 = System.currentTimeMillis();
        mergeSortPro(array2, tempArray2, 0, length-1);
        long end2 = System.currentTimeMillis();
//        System.out.println(Arrays.toString(array2));

        long start3 = System.currentTimeMillis();
        mergeSortProMax(array3, tempArray3, 0, length-1);
        long end3 = System.currentTimeMillis();
//        System.out.println(Arrays.toString(array2));

        System.out.println("优化前排序"+length+"个元素用时: "+(end1-start1));
        System.out.println("优化后排序（加了逆转右侧）"+length+"个元素用时: "+(end2-start2));
        System.out.println("再优化排序（加了插入排序）"+length+"个元素用时: "+(end3-start3));
    }

    //归并排序：时间复杂度O(nlogn)，空间复杂度O(n)
    public static <T extends Comparable> void mergeSort(T[] array, T[] tempArray, int left, int right){//array为待排序数组，left和right为两端下标
        int middle;
        if(left<right){//如果序列中只有0或1个记录，就不用排序
            middle = (left+right)/2;//从中间划分两个子序列
            mergeSort(array, tempArray, left, middle);//对左边一半进行递归
            mergeSort(array, tempArray, middle+1, right);//对右边一半进行递归
            merge(array, tempArray, left, right, middle);//进行归并
        }
    }

    //两个有序子序列都从左向右扫描，归并到新数组
    public static <T extends Comparable> void merge(T[] array, T[] tempArray, int left, int right, int middle){
        int i, index1, index2;
        for(i=left; i<=right; i++){//将数组暂存入临时数组
            tempArray[i] = array[i];
        }
        index1 = left;
        index2 = middle+1;
        i = left;
        while(index1<=middle && index2<=right){
            //取较小者插入合并数组中
            if(tempArray[index1].compareTo(tempArray[index2])<=0){//为了保证稳定性，相等时左边优先
                array[i++] = tempArray[index1++];
            }else{
                array[i++] = tempArray[index2++];
            }
        }
        while(index1<=middle){//只剩左序列，可以直接复制
            array[i++] = tempArray[index1++];
        }
        while(index2<=right){//与上个循环互斥，直接复制剩余的右序列
            array[i++] = tempArray[index2++];
        }
    }

    /*归并排序也有改进的余地。下面是R.Sedgewick发明的一个优化归并排序方法，
    在把数组暂时复制到临时数组时，将第二个子数组中元素的顺序颠倒了一下。
    这样，两个子数组从两端开始处理，向中间推进，使得这两个子数组的两端互相成为另一个数组的“监视哨”，
    从而不用像原分治法那样需要检查子序列结束的情况。
    另外，当子数组小于某个长度（如28）时，也不继续递归，而是对整个序列使用插入排序。
    经过此种优化后，归并排序算法确实更快了一些，但是复杂度数量级依然没有改变，时间和空间复杂度都与优化前一致。
    详见mergeSortPro和mergePro。
     */

    public static <T extends Comparable> void mergeSortProMax(T[] array, T[] tempArray, int left, int right){//array为待排序数组，left/right为两端
        int middle;
        if(right-left+1>THRESHOLD){//如果序列长度大于阈值（28最佳），递归进行归并
            middle = (left+right)/2;//从中间划分为两个子序列
            mergeSortPro(array, tempArray, left, middle);
            mergeSortPro(array, tempArray, middle+1, right);
            mergePro(array, tempArray, left, right, middle);
        } else {
            InsertionSort.insertionSortProMaxPlus(array, left, right);
        }
    }

    public static <T extends Comparable> void mergeProMax(T[] array, T[] tempArray, int left, int right, int middle){
        int i, k, index1, index2;//index1和index2是两个子序列的起始位置
        for(i=left; i<=middle; i++){
            tempArray[i] = array[i]; //复制左边的子序列
        }
        //复制右边的子序列，但顺序颠倒过来：
        for(i=right; i>=middle+1; i--){
            tempArray[i] = array[right+middle+1-i];
        }
        //开始归并，取较小者插入合并数组中
        for(index1=left, index2=right, k=left; k<=right; k++){
            if(tempArray[index1].compareTo(tempArray[index2])<=0){//为保证稳定性，相等时左边优先
                array[k] = tempArray[index1++];
            } else {
                array[k] = tempArray[index2--];
            }
        }
    }



    public static <T extends Comparable> void mergeSortPro(T[] array, T[] tempArray, int left, int right){//array为待排序数组，left/right为两端
        int middle;
        if(left<right){//如果序列长度大于阈值（28最佳），递归进行归并
            middle = (left+right)/2;//从中间划分为两个子序列
            mergeSortPro(array, tempArray, left, middle);
            mergeSortPro(array, tempArray, middle+1, right);
            mergePro(array, tempArray, left, right, middle);
        }
    }

    public static <T extends Comparable> void mergePro(T[] array, T[] tempArray, int left, int right, int middle){
        int i, k, index1, index2;//index1和index2是两个子序列的起始位置
        for(i=left; i<=middle; i++){
            tempArray[i] = array[i]; //复制左边的子序列
        }
        //复制右边的子序列，但顺序颠倒过来：
        for(i=right; i>=middle+1; i--){
            tempArray[i] = array[right+middle+1-i];
        }
        //开始归并，取较小者插入合并数组中
        for(index1=left, index2=right, k=left; k<=right; k++){
            if(tempArray[index1].compareTo(tempArray[index2])<=0){//为保证稳定性，相等时左边优先
                array[k] = tempArray[index1++];
            } else {
                array[k] = tempArray[index2--];
            }
        }
    }
}
